package 中等.栈;

import java.util.*;

/**
 * 给你一个大小为 n 下标从 0 开始的整数数组 nums 和一个正整数 k 。
 * 对于 k <= i < n - k 之间的一个下标 i ，如果它满足以下条件，我们就称它为一个 好 下标：
 * <p>
 * 下标 i 之前 的 k 个元素是 非递增的 。
 * 下标 i 之后 的 k 个元素是 非递减的 。
 * 按 升序 返回所有好下标。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/find-all-good-indices/
 */
public class 找到所有好下标_6190 {

    public static void main(String[] args) {

    }

    /**
     * 单调栈+哈希表
     * 保证栈的元素是单调的并且是数组连续的
     *
     * @param nums
     * @param k
     * @return
     */
    public static List<Integer> goodIndices(int[] nums, int k) {
        List<Integer> list = new ArrayList<>();
        Set<Integer> set = new HashSet<>();

        Deque<Integer> stack = new ArrayDeque<>();
        int idx = 0;
        while (idx < nums.length) {
            if (stack.size() >= k) {
                set.add(idx);
            }
            if (!stack.isEmpty() && stack.peekFirst() < nums[idx]) {
                // 注意：单调栈里面的元素必须是连续的！！！
                stack.clear();
            }
            stack.addFirst(nums[idx]);
            idx++;
        }

        idx = nums.length - 1;
        stack.clear();
        while (idx >= 0) {
            if (stack.size() >= k && set.contains(idx)) {
                // 升序排序
                list.add(0, idx);
            }
            if (!stack.isEmpty() && stack.peekFirst() < nums[idx]) {
                stack.clear();
            }
            stack.addFirst(nums[idx]);
            idx--;
        }

        return list;
    }

}
